/**
 * @file knapsack.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-22
 * 
 * @copyright Copyright (c) 2021
 * 
 * 0-1 背包
 * N个物品, 容量为W的背包，每个物品都有重量wt[i]和价值val[i]，最多能装的价值？
 * 每个物品只能选一次
 * 
 * 完全背包
 * 每个物品可以选多次
 */

#include <iostream>
#include <vector>
using namespace std;

// N个物品, 容量为W的背包
// N == wt.size() == val.size()
int knapsack(int W, int N, vector<int> &wt, vector<int> &val)
{
    // dp[i][j] 0-i的物品，背包容量j时的最大价值
#if 0
    vector<vector<int>> dp(N, vector<int>(W + 1, 0));
    // dp[i][0] = 0;
    for (int j = 0; j < wt[0]; ++j) {
        dp[0][j] = 0;
    }
    for (int j = wt[0]; j < W + 1; ++j) {
        dp[0][j] = val[0];
    }
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < W + 1; ++j) {
            if (j < wt[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wt[i]] + val[i]);
            }
        }
    }
    return dp[N - 1][W];
#endif
#if 1
    // 1. 滚动数组下，遍历背包为何要倒序？
    // 一维如果顺序遍历背包，dp[j-wt[i]]是当前轮刚更新过的
    // 而二维中的dp[i-1][j-wt[i]]是上一轮的，倒序遍可以解决这个问题
    // 因此一维遍历背包**必须**倒序，二维可正可倒
    // 2. 两个for循环能互换吗？ 二维可以，一维不可以。
    // 需要保证每个物品只取一件，倒序遍历背包如果放在前，整个dp只取一个物品
    vector<int> dp(W + 1, 0);
    dp[0] = 0;
    for (int i = 0; i < N; ++i) {          // 物品
        for (int j = W; j >= wt[i]; --j) { // 背包
            dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);
        }
    }
    return dp[W];
#endif
}

int complete_knapsack(int W, int N, vector<int> &wt, vector<int> &val)
{
    // 完全背包，每个物品可以取无限次
    // 1. 因此遍历背包时，**必须**顺序遍历
    // 2. 两个for循环的遍历顺序可以互换吗？
    // 因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。
    // 只要保证下标j之前的dp[j]都是经过计算的就可以了。
    vector<int> dp(W + 1, 0);
    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = wt[i]; j <= W; ++j) {
            dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

int main()
{
    int N = 3;
    int W = 4;
    vector<int> wt = {2, 1, 3};
    vector<int> val = {4, 2, 3};
    cout << knapsack(W, N, wt, val) << endl;
    cout << complete_knapsack(W, N, wt, val) << endl;
    return 0;
}
